{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4.3 The substitution method for solving recurrences"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.3-1\n",
    "\n",
    "> Show that the solution of $T(n) = T(n-1) + n$ is $O(n^2)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Suppose $T(n) \\le n^2$\n",
    "\n",
    "$$\n",
    "\\begin{array}{lll}\n",
    "T(n) & \\le & \\displaystyle (n-1)^2 + n  \\\\\n",
    "     &   = & \\displaystyle n^2 - 2n + 1 + n \\\\\n",
    "     &   = & \\displaystyle n^2 - n + 1 \\\\\n",
    "     & \\le & \\displaystyle n^2\n",
    "\\end{array}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.3-2\n",
    "\n",
    "> Show that the solution of $T(n) = T(\\left \\lceil n / 2 \\right \\rceil) + 1$ is $O(\\lg n)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Suppose $T(n) \\le c\\lg(n-1)$\n",
    "\n",
    "$$\n",
    "\\begin{array}{llll}\n",
    "T(n) & \\le & \\displaystyle c\\lg(\\left \\lceil n/2 \\right \\rceil - a) + 1 & \\\\\n",
    "     & \\le & \\displaystyle c\\lg(\\frac{n+1}{2} - a) + 1 & \\\\\n",
    "     &  =  & \\displaystyle c\\lg(n + 1 - 2a) - c + 1 & \\\\\n",
    "     & \\le & \\displaystyle c\\lg(n - a) - c + 1 & \\displaystyle (a \\ge \\frac{1}{3}) \\\\\n",
    "     & \\le & \\displaystyle c\\lg(n - a) & \\displaystyle (c \\ge 1)\n",
    "\\end{array}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.3-3\n",
    "\n",
    "> We saw that the solution of $T(n) = 2T(\\left \\lfloor n / 2 \\right \\rfloor) + n$ is $O(n \\lg n)$. Show that the solution of this recurrence is also $\\Omega(n \\lg n)$. Conclude that the solution is $\\Theta(n \\lg n)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Suppose $T(n) \\ge cn \\lg n$\n",
    "\n",
    "$$\n",
    "\\begin{array}{llll}\n",
    "T(n) & \\ge & \\displaystyle 2c(n/2)\\lg(n/2)+n & \\\\\n",
    "     &  =  & \\displaystyle cn\\lg n - cn + n & \\\\\n",
    "     & \\ge & \\displaystyle cn\\lg n & (c \\le 1)\n",
    "\\end{array}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.3-4\n",
    "\n",
    "> Show that by making a different inductive hypothesis, we can overcome the difficulty with the boundary condition $T(1) = 1$ for recurrence (4.19) without adjusting the boundary conditions for the inductive proof."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Suppose $T(n) \\le cn \\lg n + n$\n",
    "\n",
    "$$\n",
    "\\begin{array}{llll}\n",
    "T(n) & \\le & \\displaystyle cn\\lg n - 2n + n & \\\\\n",
    "     & \\le & \\displaystyle cn\\lg n + n &\n",
    "\\end{array}\n",
    "$$\n",
    "\n",
    "When $n=1$, $T(n)=0+1=1$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.3-5\n",
    "\n",
    "> Show that $\\Theta(n\\lg n)$ is the solution to the \"exact\" recurrence (4.3) for merge sort."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We know $T(n) = T(\\left \\lceil n / 2 \\right \\rceil) + T(\\left \\lfloor n / 2 \\right \\rfloor) + n$ is $O(n \\lg n)$.\n",
    "\n",
    "Based on 4.3-3, $T(n)$ is $\\Omega(n \\lg n)$.\n",
    "\n",
    "Therefore, $T(n)$ is $\\Theta(n\\lg n)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.3-6\n",
    "\n",
    "> Show that the solution to $T(n)=2T(\\left \\lfloor n/2 \\right \\rfloor + 17) + n$ is $O(n \\lg n)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Suppose $T(n) \\le c(n-a)\\lg(n-a)$\n",
    "\n",
    "$$\n",
    "\\begin{array}{llll}\n",
    "T(n) & \\le & \\displaystyle c(n+34-2a)\\lg(n+34-2a) & \\\\\n",
    "     & \\le & \\displaystyle c(n-a)\\lg(n-a) & (a \\ge 34)\n",
    "\\end{array}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.3-7\n",
    "\n",
    "> Using the master method in Section 4.5, you can show that the solution to the recurrence $T(n)=4T(n/3)+N$ is $T(n)=\\Theta(n^{\\log_34})$. Show that a substitution proof with the assumption $T(n) \\le n^{\\log_34}$ fails. Then show how to subtract off a lower-order term to make a substitution proof work."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Suppose $T(n) \\le cn^{\\log_34}$\n",
    "\n",
    "$$\n",
    "T(n) \\le cn^{\\log_34}+n\n",
    "$$\n",
    "\n",
    "Suppose $T(n) \\le cn^{\\log_34} - an$\n",
    "\n",
    "$$\n",
    "\\begin{array}{llll}\n",
    "T(n) & \\le & \\displaystyle cn^{\\log_34} + (1 - \\frac{4}{3})n & \\\\\n",
    "     & \\le & \\displaystyle cn^{\\log_34} - an & (a \\ge 3)\n",
    "\\end{array}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.3-8\n",
    "\n",
    "> Using the master method in Section 4.5, you can show that the solution to the recurrence $T(n)=4T(n/2)+n$ is $T(n)=\\Theta(n^2)$. Show that a substitution proof with the assumption $T(n)=cn^2$ fails. Then show how to subtract off a lower-order term to make a substitution proof work."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Suppose $T(n) \\le cn^2$\n",
    "\n",
    "$$\n",
    "T(n) \\le cn^2+n\n",
    "$$\n",
    "\n",
    "Suppose $T(n) \\le cn^2 - an$\n",
    "\n",
    "$$\n",
    "\\begin{array}{llll}\n",
    "T(n) & \\le & cn^2 + (1 - 2a)n & \\\\\n",
    "     & \\le & cn^2 - an & (a \\ge \\frac{1}{3})\n",
    "\\end{array}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.3-9\n",
    "\n",
    "> Solve the recurrence $T(n)=3T(\\sqrt{n}) + \\log n$ by making a change of variables. Your solution should be  are integral."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let $n=2^m$\n",
    "\n",
    "$T(2^m)=3T(2^{m/2}) + m$\n",
    "\n",
    "$S(m) = 3S(m/2)+m$\n",
    "\n",
    "$S(m)=\\Theta(m^{\\lg 3})$\n",
    "\n",
    "$T(n) = \\Theta({\\lg^{\\lg 3} n})$"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
